// @algorithm @lc id=100283 lang=cpp
// @title zhong-jian-er-cha-shu-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> hash;

public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int n = preorder.size();
        if (n == 0) {
            return nullptr;
        }
        for (int i = 0; i < n; ++i) {
            hash[inorder[i]] = i;
        }
        return helper(preorder, 0, n - 1, 0, n - 1);
    }

    TreeNode *helper(vector<int> &preorder, int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right) {
            return nullptr;
        }
        int pre_root = pre_left;
        int in_root = hash[preorder[pre_root]];
        int left_size = in_root - in_left;
        TreeNode *root = new TreeNode(preorder[pre_root]);
        root->left = helper(preorder, pre_left + 1, pre_left + left_size, in_left, in_root - 1);
        root->right = helper(preorder, pre_left + left_size + 1, pre_right, in_root + 1, in_right);
        return root;
    }
};